{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Decode the Slanted Ciphertext"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: decodeCiphertext"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #解码斜向换位密码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>字符串 <code>originalText</code> 使用 <strong>斜向换位密码</strong> ，经由 <strong>行数固定</strong> 为 <code>rows</code> 的矩阵辅助，加密得到一个字符串 <code>encodedText</code> 。</p>\n",
    "\n",
    "<p><code>originalText</code> 先按从左上到右下的方式放置到矩阵中。</p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/11/07/exa11.png\" style=\"width: 300px; height: 185px;\" />\n",
    "<p>先填充蓝色单元格，接着是红色单元格，然后是黄色单元格，以此类推，直到到达 <code>originalText</code> 末尾。箭头指示顺序即为单元格填充顺序。所有空单元格用 <code>' '</code> 进行填充。矩阵的列数需满足：用 <code>originalText</code> 填充之后，最右侧列 <strong>不为空</strong> 。</p>\n",
    "\n",
    "<p>接着按行将字符附加到矩阵中，构造&nbsp;<code>encodedText</code> 。</p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/11/07/exa12.png\" style=\"width: 300px; height: 200px;\" />\n",
    "<p>先把蓝色单元格中的字符附加到 <code>encodedText</code> 中，接着是红色单元格，最后是黄色单元格。箭头指示单元格访问顺序。</p>\n",
    "\n",
    "<p>例如，如果 <code>originalText = \"cipher\"</code> 且 <code>rows = 3</code> ，那么我们可以按下述方法将其编码：</p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/25/desc2.png\" style=\"width: 281px; height: 211px;\" />\n",
    "<p>蓝色箭头标识 <code>originalText</code> 是如何放入矩阵中的，红色箭头标识形成 <code>encodedText</code> 的顺序。在上述例子中，<code>encodedText = \"ch&nbsp; &nbsp;ie&nbsp; &nbsp;pr\"</code> 。</p>\n",
    "\n",
    "<p>给你编码后的字符串 <code>encodedText</code> 和矩阵的行数 <code>rows</code> ，返回源字符串 <code>originalText</code> 。</p>\n",
    "\n",
    "<p><strong>注意：</strong><code>originalText</code> <strong>不</strong> 含任何尾随空格 <code>' '</code> 。生成的测试用例满足 <strong>仅存在一个</strong> 可能的 <code>originalText</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>encodedText = \"ch   ie   pr\", rows = 3\n",
    "<strong>输出：</strong>\"cipher\"\n",
    "<strong>解释：</strong>此示例与问题描述中的例子相同。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/26/exam1.png\" style=\"width: 250px; height: 168px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>encodedText = \"iveo    eed   l te   olc\", rows = 4\n",
    "<strong>输出：</strong>\"i love leetcode\"\n",
    "<strong>解释：</strong>上图标识用于编码 originalText 的矩阵。 \n",
    "蓝色箭头展示如何从 encodedText 找到 originalText 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/26/eg2.png\" style=\"width: 300px; height: 51px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>encodedText = \"coding\", rows = 1\n",
    "<strong>输出：</strong>\"coding\"\n",
    "<strong>解释：</strong>由于只有 1 行，所以 originalText 和 encodedText 是相同的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/26/exam3.png\" style=\"width: 150px; height: 101px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>encodedText = \" b  ac\", rows = 2\n",
    "<strong>输出：</strong>\" abc\"\n",
    "<strong>解释：</strong>originalText 不能含尾随空格，但它可能会有一个或者多个前置空格。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= encodedText.length &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>encodedText</code> 仅由小写英文字母和 <code>' '</code> 组成</li>\n",
    "\t<li><code>encodedText</code> 是对某个 <strong>不含</strong> 尾随空格的 <code>originalText</code> 的一个有效编码</li>\n",
    "\t<li><code>1 &lt;= rows &lt;= 1000</code></li>\n",
    "\t<li>生成的测试用例满足 <strong>仅存在一个</strong> 可能的 <code>originalText</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [decode-the-slanted-ciphertext](https://leetcode.cn/problems/decode-the-slanted-ciphertext/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [decode-the-slanted-ciphertext](https://leetcode.cn/problems/decode-the-slanted-ciphertext/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"ch   ie   pr\"\\n3', '\"iveo    eed   l te   olc\"\\n4', '\"coding\"\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        cols = len(encodedText) // rows\n",
    "        if rows == 1:\n",
    "            return encodedText\n",
    "        ans = ''\n",
    "        for j in range(cols):\n",
    "            i = 0\n",
    "            while i<rows and j <cols:\n",
    "                ans += encodedText[i * cols + j]\n",
    "                i += 1\n",
    "                j += 1\n",
    "        return ans.rstrip(' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        col = len(encodedText)//rows\n",
    "        # def zuibiao(index):\n",
    "        #     return index//col,index%col\n",
    "        def zuibiao2index(x,y):\n",
    "            return x*col + y \n",
    "        # 差值是从0，到col-row的\n",
    "        def traverse(cha):\n",
    "            res = ''\n",
    "            for i in range(rows):\n",
    "                x = i \n",
    "                y = i+cha\n",
    "                index = zuibiao2index(x,y)\n",
    "                if index < len(encodedText):\n",
    "                    res += encodedText[index]\n",
    "                else:\n",
    "                    return res\n",
    "\n",
    "        res = ''\n",
    "        for cha in range(col+1):\n",
    "            for i in range(rows):\n",
    "                x = i \n",
    "                y = i+cha\n",
    "                index = zuibiao2index(x,y)\n",
    "                if index < len(encodedText):\n",
    "                    res += encodedText[index]\n",
    "                else:\n",
    "                    return res.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        ans = ''\n",
    "        n = len(encodedText)\n",
    "        nc = n - encodedText.count(\" \")\n",
    "        cols = n // rows\n",
    "\n",
    "        for j in range(cols):\n",
    "            i = 0\n",
    "            while 0 <= i < rows and 0 <= j < cols and nc:\n",
    "                ans += encodedText[i*cols+j]\n",
    "                if encodedText[i*cols+j].isalpha():\n",
    "                    nc -= 1\n",
    "                i += 1\n",
    "                j += 1\n",
    "                \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        length = len(encodedText)\n",
    "        col = int(length / rows)\n",
    "        s = ''\n",
    "        for j in range(col):\n",
    "            for i in range(rows):\n",
    "                if (index := i * col + j + i) < length:\n",
    "                    s += encodedText[index]\n",
    "        return s.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, text: str, m: int) -> str:\n",
    "        l = len(text)\n",
    "        n = l // m\n",
    "        ans = ''\n",
    "        for start in range(n):\n",
    "            for i in range(start, l, n+1):\n",
    "                ans += text[i]\n",
    "        return ans.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        result=''\n",
    "        cols=len(encodedText)//rows\n",
    "        for i in range(cols):\n",
    "            j=0\n",
    "            while j<rows and j+i<cols:\n",
    "                result+=encodedText[(cols+1)*j+i]\n",
    "                j+=1\n",
    "        return result.rstrip(' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        n = len(encodedText)\n",
    "        cols = n // rows\n",
    "        result = ''\n",
    "        for j in range(cols):\n",
    "            x = j\n",
    "            while(x < n):\n",
    "                result += encodedText[x]\n",
    "                x += 1 + cols\n",
    "        return result.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        col = len(encodedText)//rows\n",
    "        def zuibiao2index(x,y):\n",
    "            return x*col + y \n",
    "        res = ''\n",
    "        for cha in range(col+1):\n",
    "            for i in range(rows):\n",
    "                x = i \n",
    "                y = i+cha\n",
    "                index = zuibiao2index(x,y)\n",
    "                if index < len(encodedText):\n",
    "                    res += encodedText[index]\n",
    "                else:\n",
    "                    return res.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        total = len(encodedText)\n",
    "        columns = total // rows\n",
    "        s = ''\n",
    "        for j in range(columns):\n",
    "            for i in range(min(rows, columns - j)):\n",
    "                s += encodedText[i * columns + i + j]\n",
    "        return s.rstrip(' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        n = len(encodedText)\n",
    "        ans = ''\n",
    "        i, j, k, cols = 0, 0, 0, len(encodedText) // rows\n",
    "        while k < cols:\n",
    "            ans += encodedText[i * cols + j]\n",
    "            i += 1\n",
    "            j += 1 \n",
    "            if i == rows or j == cols:\n",
    "                k += 1\n",
    "                i, j = 0, k\n",
    "        return ans.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        n = len(encodedText)\n",
    "        cols = n // rows\n",
    "        result = ''\n",
    "        for j in range(cols):\n",
    "            x = j\n",
    "            while(x < n):\n",
    "                result += encodedText[x]\n",
    "                x += 1 + cols\n",
    "        return result.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        flag = len(encodedText)\n",
    "        #print(\"asdf->>>\",flag)\n",
    "        m = flag // rows\n",
    "        res = ''\n",
    "        for i in range(m):\n",
    "            for j in range(rows):\n",
    "                #print(encodedText[j * m + i+j],j * m + i+j)\n",
    "                if j*m+i+j>=flag:\n",
    "                    break\n",
    "                #print(encodedText[j * m + i+j])\n",
    "                res += encodedText[j * m + i+j]\n",
    "        ff  =0\n",
    "        for i in range(len(res)-1,-1,-1):\n",
    "            if res[i]!=' ':\n",
    "                ff = i\n",
    "                break\n",
    "        return res[:ff+1]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, text: str, m: int) -> str:\n",
    "        l = len(text)\n",
    "        n = l // m\n",
    "        ans = ''\n",
    "        for start in range(n-m+2):\n",
    "            for i in range(start, l, n+1):\n",
    "                ans += text[i]\n",
    "        return ans.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        length = len(encodedText)\n",
    "        col = int(length / rows)\n",
    "        s = ''\n",
    "        for j in range(col):\n",
    "            for i in range(rows):\n",
    "                index = i * col + j + i\n",
    "                if index < length:\n",
    "                    s += encodedText[index]\n",
    "        return s.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        if encodedText=='':\n",
    "            return ''\n",
    "        c=len(encodedText)//rows\n",
    "        ans=''\n",
    "        for i in range(c):\n",
    "            ans=ans+encodedText[i::c+1]\n",
    "        i=len(ans)-1\n",
    "        while ans[i]==' ':\n",
    "            i-=1\n",
    "        return ans[:i+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        n = len(encodedText)\n",
    "        ans = ''\n",
    "        i, j, k, cols = 0, 0, 0, len(encodedText) // rows\n",
    "        while k < cols:\n",
    "            ans += encodedText[i * cols + j]\n",
    "            i += 1\n",
    "            j += 1 \n",
    "            if i == rows or j == cols:\n",
    "                k += 1\n",
    "                i, j = 0, k\n",
    "        return ans.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        cols = len(encodedText)//rows\n",
    "        ret = \"\"\n",
    "        for c in range(cols):\n",
    "            for r in range(rows):\n",
    "                #获取r,c+r的字符\n",
    "                if c+r>=cols:\n",
    "                    break\n",
    "                ret += encodedText[r*cols+c+r]\n",
    "        \n",
    "        return ret.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        m = rows\n",
    "        nn = len(encodedText)\n",
    "        n = nn // m\n",
    "        ans = ''\n",
    "        for j in range(n):\n",
    "            idx = j\n",
    "            for i in range(m):\n",
    "                if i * n + idx >= nn:\n",
    "                    break\n",
    "                ans += encodedText[i * n + idx]\n",
    "                idx += 1\n",
    "\n",
    "        return ans.rstrip(' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        c=len(encodedText)//rows\n",
    "        k = 0\n",
    "        s = ''\n",
    "        while 1:\n",
    "            i = 0\n",
    "            j = k\n",
    "            while i < rows:\n",
    "                x = i*c+j\n",
    "                i += 1\n",
    "                j += 1\n",
    "                if x >= len(encodedText):\n",
    "                    return s.rstrip()\n",
    "                s += encodedText[x]\n",
    "            k += 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        # m, n = rows, len(encodedText) // rows\n",
    "        # ans = []\n",
    "        # for j in range(n):\n",
    "        #     if encodedText[0][j] == ' ':\n",
    "        #         break\n",
    "        #     for i in range(m):\n",
    "        #         if j + i < n:\n",
    "        #             ans.append(encodedText[i][j + i])\n",
    "        #         else:\n",
    "        #             break\n",
    "        # return ' '.join(ans)\n",
    "        m, n = rows, len(encodedText) // rows\n",
    "        ans = []\n",
    "        for j in range(n - m + 2):\n",
    "            for i in range(m):\n",
    "                if j + i < n:\n",
    "                    ans.append(encodedText[i*n + j + i])\n",
    "                else:\n",
    "                    break\n",
    "        return ''.join(ans).rstrip()\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        cols = len(encodedText) // rows\n",
    "        width = w = cols - (rows - 1)\n",
    "        if cols == 0: return ''\n",
    "        r = []\n",
    "        for i in range(rows):\n",
    "            for j in range(i * cols + i + w, i * cols + cols):\n",
    "                if encodedText[j] != ' ':\n",
    "                    width = max(width, j - (i * cols + i) + 1)\n",
    "        for i in range(rows):\n",
    "            r.append(encodedText[i * cols + i: i * cols + i + width])\n",
    "            if len(r[-1]) < width:\n",
    "                r[-1] = r[-1] + ' ' * (width - len(r[-1]))\n",
    "        # print(r)\n",
    "        ans = [''.join(x) for x in zip(*r)]\n",
    "        return ''.join(ans).rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        cols = len(encodedText) // rows   # 辅助矩阵的列数\n",
    "        res = []   # 遍历到的字符\n",
    "        for i in range(cols):\n",
    "            # 从左至右枚举每一条路径\n",
    "            r = 0\n",
    "            c = i\n",
    "            while r < rows and c < cols:\n",
    "                res.append(encodedText[r*cols+c])\n",
    "                r += 1\n",
    "                c += 1\n",
    "        # 删去末尾空格\n",
    "        while res and res[-1] == ' ':\n",
    "            res.pop()\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        cols=len(encodedText)//rows\n",
    "        res =[]\n",
    "        for i in range(cols):\n",
    "            r=0\n",
    "            c=i\n",
    "            while r<rows and c<cols:\n",
    "                res.append(encodedText[r*cols+c])\n",
    "                r+=1\n",
    "                c+=1\n",
    "        while res and res[-1]==' ':\n",
    "            res.pop()\n",
    "        return \"\".join(res)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        m, n = rows, len(encodedText) // rows\n",
    "        ans = []\n",
    "        for j in range(n - m + 2):\n",
    "            for i in range(m):\n",
    "                if j + i < n:\n",
    "                    ans.append(encodedText[i*n + j + i])  # encodedText[i][j + i]\n",
    "        return ''.join(ans).rstrip()\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        cols = len(encodedText) // rows   # 辅助矩阵的列数\n",
    "        res = []   # 遍历到的字符\n",
    "        for i in range(cols):\n",
    "            # 从左至右枚举每一条路径\n",
    "            r = 0\n",
    "            c = i\n",
    "            while r < rows and c < cols:\n",
    "                res.append(encodedText[r*cols+c])\n",
    "                r += 1\n",
    "                c += 1\n",
    "        # 删去末尾空格\n",
    "        while res and res[-1] == ' ':\n",
    "            res.pop()\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        cols = len(encodedText) // rows\n",
    "        width = cols\n",
    "        if cols == 0: return ''\n",
    "        r = []\n",
    "        for i in range(rows):\n",
    "            r.append(encodedText[i * cols + i: i * cols + cols])\n",
    "            if len(r[-1]) < width:\n",
    "                r[-1] = r[-1] + ' ' * (width - len(r[-1]))\n",
    "        ans = [''.join(x) for x in zip(*r)]\n",
    "        return ''.join(ans).rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        cols = len(encodedText) // rows\n",
    "        if cols == 0: return ''\n",
    "        r = []\n",
    "        for i in range(rows):\n",
    "            r.append(encodedText[i * cols + i: i * cols + cols])\n",
    "            if len(r[-1]) < cols:\n",
    "                r[-1] = r[-1] + ' ' * (cols - len(r[-1]))\n",
    "        ans = [''.join(x) for x in zip(*r)]\n",
    "        return ''.join(ans).rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        cols = len(encodedText) // rows\n",
    "        mat = [[' '] * cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                mat[i][j] = encodedText[cols * i + j]\n",
    "\n",
    "        decoded = \"\"\n",
    "        for start in range(cols):\n",
    "            r, c = 0, start\n",
    "            while r < rows and c < cols:\n",
    "                decoded += mat[r][c]\n",
    "                r += 1; c += 1\n",
    "\n",
    "        return decoded.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        n = len(encodedText)\n",
    "        cols = n // rows\n",
    "        metric = [[encodedText[c] for c in range(i * cols, cols + i*cols)] for i in range(rows) ]\n",
    "        #print(metric)\n",
    "        res = ''\n",
    "        x = 0\n",
    "        flag = True\n",
    "        while x < cols and flag:\n",
    "            for i in range(rows):\n",
    "                if x + i == cols:\n",
    "                    flag = False\n",
    "                    break \n",
    "                res += metric[i][i + x]\n",
    "            x += 1\n",
    "        \n",
    "        return res.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, en: str, rows: int) -> str:\n",
    "        n = len(en)\n",
    "        col = n // rows\n",
    "        v = []\n",
    "      \n",
    "        l = 0\n",
    "        \n",
    "        while l < n:\n",
    "            v.append(en[l:l + col])\n",
    "            l += col\n",
    "        x,y = 0,0\n",
    "        tmp = []\n",
    "        while y < col:\n",
    "            cx,cy = 0,y\n",
    "            while cx < rows and cy < col:\n",
    "                 \n",
    "                 tmp.append(v[cx][cy])\n",
    "                 cx += 1\n",
    "                 cy += 1\n",
    "            y += 1\n",
    "        return ''.join(tmp).rstrip(' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def decodeCiphertext(self, encodedText, rows):\n",
    "        cols, lentext = len(encodedText) // rows, len(encodedText)\n",
    "        return ''.join(encodedText[j] for i in range(cols) for j in range(i, lentext, cols + 1)).rstrip()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def decodeCiphertext(self, encodedText, rows):\n",
    "        cols, lentext = len(encodedText) // rows, len(encodedText)\n",
    "        return ''.join(encodedText[j] for i in range(cols) for j in range(i, lentext, cols + 1)).rstrip()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "      n = len(encodedText) \n",
    "      cols = int(n // rows)\n",
    "      return ''.join(encodedText[j] for i in range(cols) for j in range(i, n, cols + 1)).rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        width = len(encodedText) // rows \n",
    "        matrix = [ [''] * width for _ in range(rows)]\n",
    "        i, j = 0, 0\n",
    "        for ch in encodedText:\n",
    "            matrix[i][j] = ch\n",
    "            j += 1\n",
    "            if j >= width:\n",
    "                j = 0 \n",
    "                i += 1\n",
    "        res = []\n",
    "        for j in range(width):\n",
    "            i = 0\n",
    "            while i < rows and j < width:\n",
    "                res.append( matrix[i][j] )\n",
    "                i += 1\n",
    "                j += 1\n",
    " \n",
    "        while res and res[-1] == \" \":\n",
    "            res.pop()                \n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        if not encodedText or rows == 1:\n",
    "            return encodedText\n",
    "        length = len(encodedText) // rows\n",
    "        square = [[' ' for i in range(length + 1)] for j in range(rows)]\n",
    "        for i in range(rows):\n",
    "            for j in range(length):\n",
    "                square[i][j] = encodedText[i*length + j]\n",
    "        #print(square)\n",
    "        res = []\n",
    "        x = 0\n",
    "        y = 0\n",
    "        while True:\n",
    "            res.append(square[x][y])\n",
    "            if x == rows - 1 or y == length - 1:\n",
    "                y = abs(x-y)+1\n",
    "                x = 0\n",
    "            else:\n",
    "                x += 1\n",
    "                y += 1\n",
    "            if x==0 and y == length:\n",
    "                break\n",
    "        print(\"res:\", res)\n",
    "        r = ''\n",
    "        for i in range(len(res)-1, -1, -1):\n",
    "            if res[i] != ' ':\n",
    "                break\n",
    "            else:\n",
    "                res.pop()\n",
    "        \n",
    "        for i in res:\n",
    "            r = r + str(i)\n",
    "        return r\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        len_enc = len(encodedText)\n",
    "        if rows == 1:\n",
    "            return encodedText.rstrip()\n",
    "        if len_enc == 0:\n",
    "            return ''\n",
    "        lie = len_enc//rows\n",
    "        biao = [[]]*rows\n",
    "        biao_1 =list(encodedText)\n",
    "        a = ''\n",
    "        for i in range(rows):\n",
    "            biao[i]= biao[i]+biao_1[i*(lie):(i+1)*lie]\n",
    "        biao_2 = []\n",
    "        for i in range(rows):\n",
    "            biao_2.append(biao[i][i:]+[' ']*i)\n",
    "        for i in range(len(biao[0])):\n",
    "            for j in range(len(biao_2)):\n",
    "                a = a+biao_2[j][i]\n",
    "        return a.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "      n = len(encodedText)\n",
    "      if not n:\n",
    "        return encodedText\n",
    "      \n",
    "      cols, ans, last = n / rows, [' '] * n, 0\n",
    "      for i, ch in enumerate(encodedText):\n",
    "        row, col = i // cols, i % cols\n",
    "        if col >= row:\n",
    "          index = int(row + (col - row) * rows)\n",
    "          ans[index] = ch\n",
    "          if ch != ' ':\n",
    "            last = max(last, index)\n",
    "      return ''.join(i for i in ans[:last+1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "      n = len(encodedText) \n",
    "      cols, ans, last = n / rows, [' '] * n, 0\n",
    "      for i, ch in enumerate(encodedText):\n",
    "        row, col = i // cols, i % cols\n",
    "        if col >= row:\n",
    "          index = int(row + (col - row) * rows)\n",
    "          ans[index] = ch\n",
    "          if ch != ' ':\n",
    "            last = max(last, index)\n",
    "      return ''.join(i for i in ans[:last+1])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
